package 力扣.双指针.双指针;

import java.util.Deque;
import java.util.LinkedList;

public class 绝对差不超过限制的1438 {
    public static void main(String[] args) {
//        int[] ints = {8,2,4,7};
//        int[] ints = {10,1,2,4,7,2};
//        int[] ints = {4,2,2,2,4,4,2,2};
//        int[] ints = {2,2,2,2,2,4};
//        int[] ints = {2,2,2,4,4,2,5,5,5,5,5,2};
        int[] ints = {7,40,10,10,40,39,96,21,54,73,33,17,2,72,5,76,28,73,59,22,100,91,80,66,5,49,26,45,13,27,74,87,56,76,25,64,14,86,50,38,65,64,3,42,79,52,37,3,21,26,42,73,18,44,55,28,35,87};
//        int[] ints = {24,12,71,33,5,87,10,11,3,58,2,97,97,36,32,35,15,80,24,45,38,9,22,21,33,68,22,85,35,83,92,38,59,90,42,64,61,15,4,40,50,44,54,25,34,14,33,94,66,27,78,56,3,29,3,51,19,5,93,21,58,91,65,87,55,70,29,81,89,67,58,29,68,84,4,51,87,74,42,85,81,55,8,95,39};
        int i = longestSubarray(ints, 63);
        System.out.println(i);
    }
    public static int longestSubarray(int[] nums, int limit) {
        Deque<Integer> queMax = new LinkedList<Integer>();//最大值队列
        Deque<Integer> queMin = new LinkedList<Integer>();//最小值队列
        int n = nums.length;
        int left = 0, right = 0;//左、右指针
        int ret = 0;
        while (right < n) {
            while (!queMax.isEmpty() && queMax.peekLast() < nums[right]) {
                queMax.pollLast();
            }
            while (!queMin.isEmpty() && queMin.peekLast() > nums[right]) {
                queMin.pollLast();
            }
            queMax.offerLast(nums[right]);
            queMin.offerLast(nums[right]);
            while (!queMax.isEmpty() && !queMin.isEmpty() && queMax.peekFirst() - queMin.peekFirst() > limit) {
                if (nums[left] == queMin.peekFirst()) {
                    queMin.pollFirst();
                }
                if (nums[left] == queMax.peekFirst()) {
                    queMax.pollFirst();
                }
                left++;
            }
            ret = Math.max(ret, right - left + 1);
            right++;
        }
        return ret;
    }
}
